10061. Tree Минимальный элемент

Задано бинарное дерево поиска. Верните указатель на его минимальный элемент.

Определение дерева:

//Java

class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

left = null;

right = null;

}

}

// C++

class TreeNode

{

public:

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

Реализуйте функцию Minimum которая возвращает указатель на вершину с наименьшим элементом в дереве.

// Java

TreeNode Minimum(TreeNode tree)

// C++

TreeNode* Minimum(TreeNode *tree)

Пример

Функция Minimum возвращает res – указатель на вершину с наименьшим элементом в дереве.

РЕШЕНИЕ

дерево

Анализ алгоритма

Если tree = NULL, то возвращаем NULL.

Для поиска вершины с наименьшим значением следует стартовать с корня и двигаться по указателям всегда в левое поддерево до тех пор, пока левый указатель текущей вершины не станет равным NULL.

Реализация алгоритма

TreeNode *Minimum(TreeNode *tree)

{

Если tree = NULL, то возвращаем NULL.

if (tree == NULL) return tree;

Двигаемся в левое поддерево пока левый сын вершины не станет равным NULL.

while (tree->left != NULL) tree = tree->left;

Возвращаем указатель на минимальный элемент.

return tree;

}

Реализация алгоритма – рекурсия

TreeNode *Minimum(TreeNode *tree)

{

if (tree->left == NULL) return tree;

return Minimum(tree->left);

}

Java реализация

TreeNode Minimum(TreeNode tree)

{

if (tree == null) return tree;

while (tree.left != null) tree = tree.left;

return tree;

}

Java реализация – рекурсия

TreeNode Minimum(TreeNode tree)

{

if (tree.left == null) return tree;

return Minimum(tree.left);

}